package lc.q51_100;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;

/**
 * 给出一个无重叠的 ，按照区间起始端点排序的区间列表。
 *
 * 在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
 */
public class Q57 {

    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> arrs = new LinkedList<>();
        boolean hasAdd = false;
        for (int[] interval : intervals) {
            // 可能最后一下还没增
            if (hasAdd) {
                arrs.add(interval);
                continue;
            }
            if (interval[1] < newInterval[0]) {
                arrs.add(interval);
            } else if (newInterval[1] < interval[0]) {
                arrs.add(newInterval);
                arrs.add(interval);
                hasAdd = true;
            }
            else {
                // 先合并再判断
                int start = Math.min(interval[0], newInterval[0]);
                int end = Math.max(interval[1], newInterval[1]);
                newInterval = new int[]{start, end};
            }
        }
        if (!hasAdd) {
            arrs.add(newInterval);
        }
        int[][] results = new int[arrs.size()][];
        for (int i = 0; i < arrs.size(); i++) {
            results[i] = arrs.get(i);
        }
        return results;
    }

    public static void main(String[] args) {
        int[][] ints = {
                {1,2},
                {3,5},
                {6,7},
                {8,10},
                {12,16}
        };
        int[] newInterval = {4,8};
        Q57 q57 = new Q57();
        int[][] insert = q57.insert(ints, newInterval);
        for (int[] ints1 : insert) {
            System.out.println(Arrays.stream(ints1).mapToObj(String::valueOf).collect(Collectors.joining(",")));
        }
    }

}
